package com.leetcode;

import java.util.*;

/**
 * 46. 全排列
 *
 * @author fy
 * @date 2022/4/27 19:58
 */
public class Solution46 {

    private List<List<Integer>> res;
    private int n;

    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        n = nums.length;
        Set<Integer> union = new HashSet<>();
        for (int num : nums) {
            union.add(num);
        }
        dfs(union, new ArrayList<>());
        return res;
    }

    private void dfs(Set<Integer> union, List<Integer> preList) {
        // 如果长度已经到了数组的长度, 那么就已经遍历完了
        if (preList.size() == n) {
            res.add(new ArrayList<>(preList));
            return;
        }
        // 挨个遍历下一个元素
        for (Integer num : union) {
            if (!preList.contains(num)) {
                preList.add(num);
                dfs(union, preList);
                preList.remove(num);
            }
        }
    }


    public static void main(String[] args) {
        int[] nums = new int[] {1, 2, 3};
        List<List<Integer>> res = new Solution46().permute(nums);
        System.out.println(res);
    }

}
